import collections


class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """

        def search(state, u):
            p[u] = state
            for v in d[u]:
                if p[v] == -1:
                    if not search(1 - state, v):
                        return False
                else:
                    if p[v] == state:
                        return False
            return True

        n = len(graph)
        d = collections.defaultdict(set)
        for u, item in enumerate(graph):
            for v in item:
                d[u].add(v)
        p = [-1] * n
        for u in range(n):
            if p[u] == -1:
                if not search(0, u):
                    return False
        return True


data = Solution()
graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
print(data.isBipartite(graph))
graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
print(data.isBipartite(graph))
graph = [[4, 1], [0, 2], [1, 3], [2, 4], [3, 0]]
print(data.isBipartite(graph))
